package problem45_Jump_Game_II;

import java.util.Stack;

public class MySolution {
	private int minStep=0;
	public int jump(int[] nums) {
		minStep=nums.length-1;Stack<Integer> stack=new Stack<>();
		stack.push(0);
		jump(0,nums.length-1,nums,stack);
		return minStep;
	}
	
	private void jump(int start,int end,int[] nums,Stack<Integer> stack){
		if(end-start<=nums[start]){
			int currentStep=stack.peek();
			minStep=Math.min(end==start?currentStep:currentStep+1, minStep);
		}else{
			for(int i=1;i<=nums[start];i++){
				int currentStep=stack.peek();
				stack.push(currentStep+1);
				jump(start+i,end,nums,stack);
				stack.pop();
			}
			
		}
	}
	
	public static void main(String[] args){
		System.out.println(new MySolution().jump(new int[]{2,3,1,1,4,1}));
	}
}
